package Top_Interview_Questions_Review._008Two_Pointers;


import Top_Interview_Questions_Review.ListNode;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/10 17:46
 * <p>
 * 功能描述:
 */
public class _0234 {

    public static void main(String[] args) {
        _0234 test = new _0234();
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
//        ListNode node5 = new ListNode(4);
        ListNode node6 = new ListNode(3);
        ListNode node7 = new ListNode(2);
        ListNode node8 = new ListNode(1);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
//        node4.next = node5;
        node4.next = node6;
        node6.next = node7;
        node7.next = node8;

        test.isPalindrome1(node1);
    }

    public boolean isPalindrome2(ListNode head) {
        if(head == null || head.next == null) {
            return true;
        }
        ListNode slow = head, fast = head;
        ListNode pre = head, prepre = null;
        while(fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
            pre.next = prepre;
            prepre = pre;
        }
        if(fast != null) {
            slow = slow.next;
        }
        while(pre != null && slow != null) {
            if(pre.val != slow.val) {
                return false;
            }
            pre = pre.next;
            slow = slow.next;
        }
        return true;
    }






    /**
     * 快慢指针+反转
     * https://leetcode-cn.com/problems/palindrome-linked-list/solution/dong-hua-yan-shi-234-hui-wen-lian-biao-by-user7439/
     */
    public boolean isPalindrome1(ListNode head) {
        //边界条件不要忘记了
        if(head==null || head.next==null) {
            return true;
        }
        ListNode p = new ListNode(-1);
        ListNode low = p;
        ListNode fast = p;
        p.next = head;
        //快慢指针不断迭代，找到中间节点
        while(fast!=null && fast.next!=null) {
            low = low.next;
            fast = fast.next.next;
        }
        ListNode cur = low.next;
        ListNode pre = null;
        low.next = null;
        low = p.next;
        //将链表一分为二之后，反转链表后半部分
        while(cur!=null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        //将链表前半部分和 反转的后半部分对比
        while(pre!=null) {
            if(low.val!=pre.val) {
                return false;
            }
            low = low.next;
            pre = pre.next;
        }
        return true;
    }


    /**
     * 转换为数组比较
     */
    public boolean isPalindrome(ListNode head) {
        if(head==null || head.next==null) {
            return true;
        }
        java.util.ArrayList<Integer> arr = new java.util.ArrayList<Integer>();
        //申请一个容器，然后把元素都放到数组中
        while(head!=null) {
            arr.add(head.val);
            head = head.next;
        }
        int i = 0;
        int j = arr.size()-1;
        //用i和j两个指针，一个往后，一个往前，不断迭代
        //如果i的值不等于j说明不是回文，反之是回文
        while(i<j) {
            if(arr.get(i).compareTo(arr.get(j))!=0) {
                return false;
            }
            ++i;
            --j;
        }
        return true;
    }

}
